1. Field of the Invention
The present invention relates to a computational method and apparatus for finite field multiplication used for an encoder and a decoder for error correction codes and the like.
2. Description of Related Art
Recent technological advances have resulted in transition from analog to digital communication. For digital communication, redundancy of signal is small because binary information represented by 0 and 1 is transmitted, and it is therefore difficult to recover data if any digital error occurs during the transmission. Under such circumstances, error correction codes have been put in use to detect and correct digital error at an receiving end. Cyclic codes are widely used as error correction codes, and a method has been proposed wherein multiplication on a Galois field is used to generate such codes.
A finite field GF(2.sup.m) is a set of 2.sup.m elements and each element is represented using exponential representation or vector representation. An element of the order 2.sup.m -1 in the finite field GF(2.sup.m) is referred to as an "primitive element". According to the exponential representation, each element is represented by an exponential i of .alpha. utilizing the fact that an arbitrary element "a" satisfies a=.alpha..sup.i where .alpha. represents an primitive element and i represents a positive integer. According to the vector representation, GF(2.sup.m) is regarded as an m dimensional vector space of GF(2), and an arbitrary element "a" is represented by an m dimensional vector (a.sub.0, a.sub.1, . . . , a.sub.m-1).
Each component ai of the vector is an element of GF(2), i.e., 0 or 1. In vector representation, a vector space is not limited to one type of basis, and representation of an element can vary depending on the basis used. The basis may be a normal basis and a polynomial basis. The normal basis is a basis as shown below. EQU (.alpha., .alpha..sup.2, .alpha..sup.2.spsp.2, . . . , .alpha..sup.2.spsp.m-1)
where the followings are linearly independent for the primitive element .alpha.. EQU .alpha., .alpha..sup.2, .alpha..sup.2.spsp.2, . . . , .alpha..sup.2.spsp.m-1
The polynomial basis a basis (1, z, z.sup.2, . . . , Z.sup.m-1) which is generated from a monic irreducible polynomial of degree m over GF(2) using an element z which is a root of f. Here, a=(a.sub.0, a.sub.1, . . . , a.sub.m-1) is regarded as an element of GF(2)[x] where x is a variable, and "a" is represented by a=a.sub.m-1 x.sup.m-1 + . . . +a.sub.1 x+a.sub.0. This representation is referred to as polynomial representation.
Addition of two elements "a" and "b" over GF(2.sup.m) is represented by a+b=(a.sub.0 +b.sub.0, a.sub.1 +b.sub.1, . . . , a.sub.m-1 +b.sub.m-1). That is, the two elements may be added over GF(2) for each component. The addition over GF(2) is carried out as Exclusive OR. In the case of exponential representation, however, it is difficult to define the method of addition uniquely. Therefore, vector representation is commonly used for representation of an element.
Conventional methods for the multiplication of two elements "a" and "b" over GF(2.sup.m) includes methods employing exponential representation, a normal base and a polynomial base. A method employing exponential representation, an index k of ab=.alpha..sup.k is computated where "a" and "b" are regarded as a=.alpha..sup.1, b=.alpha..sup.j. The multiplication of two elements "a" and "b" may be represents as follows. EQU c=ab=.alpha..sup.i+j =.alpha..sup.i+j (mod 2m-1)
Then a calculation of a reminder on an integral ring employs to obtain the index. The method employing a normal base is described in U.S. Pat. No. 4,587,627 "computational Method and Apparatus for Finite Field Arithmetic" and U.S. Pat. No. 4,745,568 "Computational Method and Apparatus for Finite Field Multiplication" and, particularly, multiplication using a normal base is described in detail in A. J. Menezes, Ed, "Applications of Finite Fields", Kluwer Academic Pub.
The method employing a polynomial base is a method wherein a multiplicand a=(a.sub.0, a.sub.1, . . . , a.sub.m-1) and a multiplier b=(b.sub.0, b.sub.1, . . . , b.sub.m-1) are respectively regarded as polynomials a=a.sub.m-1 x.sub.m-1 + . . . +a.sub.1 x+a.sub.0 and b=b.sub.m-1 x.sub.m-1 + . . . +b.sub.1 x+b.sub.0 over GF(2); "a" and "b" in the polynomial representation are subjected to polynomial multiplication over GF(2) to derive d=d.sub.2m-2 x.sup.2m-3 + . . . +d.sub.1 x+d.sub.0 which is then divided by a polynomial .function.=x.sup.m +.function..sub.m-1 x.sup.m-1 + . . . +.function..sub.1 x+.function..sub.0 ; and c=(c.sub.0, c.sub.1, . . . , c.sub.m-1) derived from the remainder c=c.sub.m-1 xm.sup.-1 + . . . +c.sub.1 x+c.sub.0 is used as the result of c=ab.
The conventional methods and circuits for multiplying two elements "a" and "b" over a finite field GF(2m) as described above have had the following problems.
The method employing exponential representation involves conversion of an element from vector representation to exponential representation. This method requires a conversion table which dimension has an exponential size. Therefore, a circuit employing the exponential representation method will be quite large in scale.
Any method employing a normal base requires m.sup.2 or more gates to be implemented in a circuit, which results in a problem in that the circuit is in a very large scale when m is large.
Further, the method employing a polynomial base involves division of a polynomial of degree 2m-1 and polynomial degree m over GF(2). This division involves an enormous amount of computing time and further results in a problem in that the scale of a circuit to implement this methods becomes too large.
The present invention has been conceived to solve the problems as described above associated with conventional methods and circuits for multiplication over a finite field, and it is an object of the invention to provide a computational method and apparatus for finite field multiplication in which computation will be carried out at high speed and in a short time and which requires a small circuit scale.